{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Square Submatrices with All Ones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSquares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计全为 1 的正方形子矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m * n</code>&nbsp;的矩阵，矩阵中的元素不是 <code>0</code> 就是 <code>1</code>，请你统计并返回其中完全由 <code>1</code> 组成的 <strong>正方形</strong> 子矩阵的个数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>matrix =\n",
    "[\n",
    "&nbsp; [0,1,1,1],\n",
    "&nbsp; [1,1,1,1],\n",
    "&nbsp; [0,1,1,1]\n",
    "]\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong> \n",
    "边长为 1 的正方形有 <strong>10</strong> 个。\n",
    "边长为 2 的正方形有 <strong>4</strong> 个。\n",
    "边长为 3 的正方形有 <strong>1</strong> 个。\n",
    "正方形的总数 = 10 + 4 + 1 = <strong>15</strong>.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>matrix = \n",
    "[\n",
    "  [1,0,1],\n",
    "  [1,1,0],\n",
    "  [1,1,0]\n",
    "]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>\n",
    "边长为 1 的正方形有 <strong>6</strong> 个。 \n",
    "边长为 2 的正方形有 <strong>1</strong> 个。\n",
    "正方形的总数 = 6 + 1 = <strong>7</strong>.\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length&nbsp;&lt;= 300</code></li>\n",
    "\t<li><code>1 &lt;= arr[0].length&nbsp;&lt;= 300</code></li>\n",
    "\t<li><code>0 &lt;= arr[i][j] &lt;= 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-square-submatrices-with-all-ones](https://leetcode.cn/problems/count-square-submatrices-with-all-ones/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-square-submatrices-with-all-ones](https://leetcode.cn/problems/count-square-submatrices-with-all-ones/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,1,1],[1,1,1,1],[0,1,1,1]]', '[[1,0,1],[1,1,0],[1,1,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, dp: List[List[int]]) -> int:\n",
    "        ans = sum(dp[0]) + sum(l[0] for l in dp) - dp[0][0]\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(1, len(dp[0])):\n",
    "                if dp[i][j]:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1\n",
    "                    ans += dp[i][j]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        ans = 0\n",
    "\n",
    "        def check(side, i, j):\n",
    "            \"\"\"检查i，j为左上角，side+1为边长的正方形是否存在\"\"\"\n",
    "            # 左下角\n",
    "            i += side\n",
    "            for x in range(0, side * 2 + 1):\n",
    "                # 出界或不为1\n",
    "                if not (-1 < i < m and -1 < j < n and matrix[i][j]):\n",
    "                    return False\n",
    "                if x < side:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i -= 1\n",
    "            return True\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]:\n",
    "                    ans += 1\n",
    "                    side = 1\n",
    "                    while check(side, i, j):\n",
    "                        ans += 1\n",
    "                        side += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if matrix[i][j] == 1:\n",
    "                    matrix[i][j] = min(matrix[i-1][j], matrix[i-1][j-1], matrix[i][j-1]) + 1\n",
    "        return sum(sum(row) for row in matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        ans = 0\n",
    "\n",
    "        def check(side, i, j):\n",
    "            \"\"\"检查i，j为左上角，side+1为边长的正方形是否存在\"\"\"\n",
    "            # 左下角\n",
    "            i += side\n",
    "            for x in range(0, side * 2 + 1):\n",
    "                # 出界或不为1\n",
    "                if not (-1 < i < m and -1 < j < n and matrix[i][j]):\n",
    "                    return False\n",
    "                if x < side:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i -= 1\n",
    "            return True\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]:\n",
    "                    ans += 1\n",
    "                    side = 1\n",
    "                    while check(side, i, j):\n",
    "                        ans += 1\n",
    "                        side += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        dp = matrix\n",
    "        nums = sum(matrix[0]) + sum(next(zip(*matrix))) - matrix[0][0]\n",
    "        for i in range(1, len(matrix)):\n",
    "            for j in range(1, len(matrix[0])):\n",
    "                if matrix[i][j]:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1\n",
    "                    nums += dp[i][j]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        ans = 0\n",
    "\n",
    "        def check(side, i, j):\n",
    "            \"\"\"检查i，j为左上角，side+1为边长的正方形是否存在\"\"\"\n",
    "            # 左下角\n",
    "            i += side\n",
    "            for x in range(0, side * 2 + 1):\n",
    "                # 出界或不为1\n",
    "                if not (-1 < i < m and -1 < j < n and matrix[i][j]):\n",
    "                    return False\n",
    "                if x < side:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i -= 1\n",
    "            return True\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]:\n",
    "                    side = 0\n",
    "                    while check(side, i, j):\n",
    "                        ans += 1\n",
    "                        side += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 or j == 0:\n",
    "                    f[i][j] = matrix[i][j]\n",
    "                elif matrix[i][j] == 0:\n",
    "                    f[i][j] = 0\n",
    "                else:\n",
    "                    f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1\n",
    "                ans += f[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [ [0]*n for _ in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 or j==0:\n",
    "                    dp[i][j] = matrix[i][j]\n",
    "                elif matrix[i][j] == 0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1\n",
    "                ans += dp[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre = [list(accumulate(mat, initial=0)) for mat in matrix]\n",
    "        ret = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(1, min(m - i, n - j)+1):\n",
    "                    tmp = 0\n",
    "                    for x in range(i, i+k):\n",
    "                        if pre[x][j+k] - pre[x][j] != k:\n",
    "                            break\n",
    "                        tmp += 1\n",
    "                    ret += (tmp == k)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        ret = 0\n",
    "        dp = matrix\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]:\n",
    "                    if i and j:\n",
    "                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1         \n",
    "                    ret += dp[i][j]\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        ret = 0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j]:\n",
    "                    if i and j:\n",
    "                        matrix[i][j] = min(matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1]) + 1         \n",
    "                    ret += matrix[i][j]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix or not matrix[0]: return 0\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        dp = [[0]* cols for _ in range(rows)]\n",
    "        total_count = 0 \n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if matrix[i][j] == 1:\n",
    "                    if i==0 or j==0:\n",
    "                        dp[i][j] = matrix[i][j]\n",
    "                    else:\n",
    "                        dp[i][j]=1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])\n",
    "                    total_count += dp[i][j]\n",
    "        return total_count\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [ [0]*n for _ in range(m)]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 or j ==0:\n",
    "                    dp[i][j] = matrix[i][j]\n",
    "                elif matrix[i][j] == 0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1\n",
    "                ans += dp[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return res\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 1:\n",
    "                    if i == 0 or j == 0:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1\n",
    "                    res += dp[i][j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        dp = matrix\n",
    "        for i in range(1, len(matrix)):\n",
    "            for j in range(1, len(matrix[0])):\n",
    "                if dp[i-1][j-1] != 0 and dp[i-1][j]!=0 and dp[i][j-1] != 0:\n",
    "                    if dp[i][j] != 0:\n",
    "                        dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1\n",
    "                else:\n",
    "                    \n",
    "                    dp[i][j] = max(dp[i][j] ,min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j], dp[i][j]))\n",
    "             \n",
    "        print(dp)\n",
    "        return sum(sum(lis) for lis in dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m ,n = len(matrix),len(matrix[0])\n",
    "\n",
    "        f = [[0]*n for _ in  range(m)]\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 or j ==0:\n",
    "                    f[i][j] = matrix[i][j]\n",
    "                elif matrix[i][j] == 0:\n",
    "                    f[i][j] =0\n",
    "                else :\n",
    "                    f[i][j] = min(f[i][j-1],f[i-1][j],f[i-1][j-1])+1\n",
    "                ans +=f[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m,n =len(matrix),len(matrix[0])\n",
    "        f =  [[0 for _ in range(n)] for _ in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 or j==0:\n",
    "                    f[i][j]=matrix[i][j]\n",
    "                elif matrix[i][j]==0:\n",
    "                        f[i][j]=0\n",
    "                else:\n",
    "                    f[i][j]=min(f[i-1][j-1],f[i][j-1],f[i-1][j])+1\n",
    "                ans =ans+f[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        cnt = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0:\n",
    "                    continue\n",
    "                if i == 0 or j == 0:\n",
    "                    dp[i][j] = 1\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1\n",
    "                cnt += dp[i][j]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        dp=[[0 for _ in range(len(matrix[0]))]for _ in range(len(matrix))]\n",
    "\n",
    "        count=0\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[i])):\n",
    "                if matrix[i][j]==1:\n",
    "                    if i==0 or j==0:\n",
    "                        dp[i][j]=1\n",
    "                    else:\n",
    "                        dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1\n",
    "                    count+=dp[i][j]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        dp = [[0] * cols for _ in range(rows)]\n",
    "\n",
    "        for i in range(rows):\n",
    "            dp[i][0] = 1 if matrix[i][0] == 1 else 0\n",
    "        for j in range(cols):\n",
    "            dp[0][j] = 1 if matrix[0][j] == 1 else 0\n",
    "        \n",
    "        for i in range(1,rows):\n",
    "            for j in range(1,cols):\n",
    "                if matrix[i][j] == 1:\n",
    "                    dp[i][j] = 1\n",
    "                    dp[i][j] += min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])\n",
    "        \n",
    "\n",
    "        ans = 0\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                ans += dp[i][j]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m,n =len(matrix),len(matrix[0])\n",
    "        f =  [[0 for _ in range(n)] for _ in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 or j==0:\n",
    "                    f[i][j]=matrix[i][j]\n",
    "                elif matrix[i][j]==0:\n",
    "                        f[i][j]=0\n",
    "                else:\n",
    "                    f[i][j]=min(f[i-1][j-1],f[i][j-1],f[i-1][j])+1\n",
    "                ans =ans+f[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        dp = [[0 for j in range(m+1)] for i in range(n+1)]\n",
    "        ans = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                if matrix[i-1][j-1] == 0:\n",
    "                    continue\n",
    "                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1\n",
    "                ans += dp[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        # print(m,n)\n",
    "        # 定义为这个位置是右下角点能做的正方形和\n",
    "        dp=[[0 for _ in range(n)] for _ in range(m)]\n",
    "        res=0\n",
    "        # print(dp)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==1:\n",
    "                    if i==0 or j==0:\n",
    "                        dp[i][j]=1\n",
    "                    else:\n",
    "                        dp[i][j]=min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1\n",
    "                    res+=dp[i][j]\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Sum2D:\n",
    "\n",
    "    def __init__(self, mat: List[List[int]]):\n",
    "        self.h = len(mat)\n",
    "        self.w = len(mat[0])\n",
    "        ms = [[0] * (self.w + 1)] + [[0] + list(accumulate(m)) for m in mat]\n",
    "        for c in range(self.w + 1):\n",
    "            for r in range(self.h):\n",
    "                ms[r + 1][c] += ms[r][c]\n",
    "        self.ms = ms\n",
    "\n",
    "    def query(self, r0, c0, r1, c1):\n",
    "        return self.ms[r1][c1] + self.ms[r0][c0] - self.ms[r1][c0] - self.ms[r0][c1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        h = len(matrix)\n",
    "        w = len(matrix[0])\n",
    "        s2d = Sum2D(matrix)\n",
    "\n",
    "        ans = 0\n",
    "        for r in range(h):\n",
    "            for c in range(w):\n",
    "                if matrix[r][c]:\n",
    "                    n = 0\n",
    "                    while r + n + 1 <= h and c + n + 1 <= w and s2d.query(r, c, r + n + 1, c + n + 1) == (n + 1) * (\n",
    "                            n + 1):\n",
    "                        n += 1\n",
    "                    ans += n\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        b=len(matrix)\n",
    "        a=len(matrix[0])\n",
    "        for i in range(a):\n",
    "            for j in range(b):\n",
    "                if i*j!=0 and int(matrix[j][i])==1:\n",
    "                    matrix[j][i]=1+min(int(matrix[j][i-1]),int(matrix[j-1][i-1]),int(matrix[j-1][i]))\n",
    "                else:\n",
    "                    matrix[j][i]=int(matrix[j][i])\n",
    "        return sum([matrix[j][i] for i in range(a) for j in range(b)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix[0])\n",
    "        n = len(matrix)\n",
    "        dp = [[0]*(m) for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i == 0 or j == 0:\n",
    "                    dp[i][j] = matrix[i][j]\n",
    "                elif matrix[i][j] == 1:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1\n",
    "                ans += dp[i][j]\n",
    "        print(dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        rownum=len(matrix)\n",
    "        colnum=len(matrix[0])\n",
    "        #list1=[]\n",
    "\n",
    "        def check(x,y,a,num):\n",
    "            ok=1\n",
    "            if x+a>rownum or y+a>colnum:\n",
    "                return num\n",
    "            \n",
    "            for i in range(x,x+a):\n",
    "                #if i>=rownum:\n",
    "                    #ok=0\n",
    "                    #break\n",
    "                for j in range(y,y+a):\n",
    "                    #if j>=colnum:\n",
    "                        #ok=0\n",
    "                        #break\n",
    "                    if matrix[i][j]!=1:\n",
    "                        ok=0\n",
    "                        break\n",
    "                if ok==0:\n",
    "                    break\n",
    "            if ok==1:\n",
    "                return check(x,y,a+1,num+1)\n",
    "            else:\n",
    "                return num \n",
    "        \n",
    "        res=0\n",
    "        for i in range(rownum):\n",
    "            for j in range(colnum):\n",
    "                if matrix[i][j]==1:\n",
    "                    aa=check(i,j,2,1)\n",
    "                    #list1.append(aa)\n",
    "                    res+=aa\n",
    "                #else:\n",
    "                    #list1.append(0)\n",
    "        \n",
    "        return res\n",
    "        #return list1\n",
    "\n",
    "\n",
    "                \n",
    "            \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 1:\n",
    "                    if i == 0 or j == 0:\n",
    "                        ans += 1\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = 1 + min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])\n",
    "                        ans += dp[i][j]\n",
    "        print(dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "\n",
    "        #以i,j为右下角的正方形的个数\n",
    "        res =[[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m): res[i][0] = 0 if matrix[i][0]==0 else 1\n",
    "        for j in range(n): res[0][j] = 0 if matrix[0][j]==0 else 1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[i][j] =  1+ min(res[i-1][j-1],res[i-1][j],res[i][j-1]) if matrix[i][j]==1 else 0\n",
    "        \n",
    "        print(res)\n",
    "        \n",
    "        return sum( sum(row) for row in res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==1:\n",
    "                    if i==0 or j==0:\n",
    "                        dp[i][j]=1\n",
    "                    else:\n",
    "                        dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1\n",
    "                    ans+=1\n",
    "        print(dp)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dp[i][j]>1:\n",
    "                    ans+=dp[i][j]-1\n",
    "        return ans  \n",
    "        #0 1 1 1\n",
    "        #1 1 2 2\n",
    "        #0 1 2 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = value = int(matrix[0][0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0 and j == 0: continue\n",
    "                if i == 0 or j == 0: \n",
    "                    dp[i][j] = 1 if matrix[i][j] == 1 else 0\n",
    "                elif matrix[i][j] == 1:\n",
    "                    dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1\n",
    "                value += dp[i][j]\n",
    "        print(dp)\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            nrows = len(matrix)\n",
    "        \n",
    "        if len(matrix[0]) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            ncols = len(matrix[0])\n",
    "        \n",
    "        dp = [[0 for i in range(ncols+1)] for _ in range(nrows+1)]\n",
    "        print(dp)\n",
    "\n",
    "        for row in range(1,nrows+1):\n",
    "            for col in range(1,ncols+1):\n",
    "                if matrix[row-1][col-1] == 1:\n",
    "                    dp[row][col] = min(dp[row-1][col], min(dp[row-1][col-1],dp[row][col-1])) + 1                    \n",
    "        result = 0\n",
    "        print(dp)\n",
    "        for i in dp:\n",
    "            result+=sum(i)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        if n == 0 or m == 0:\n",
    "            return 0\n",
    "\n",
    "        dp = [[0 for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == 0:\n",
    "                    continue\n",
    "                if matrix[i][j] == 1 and (i == 0 or j == 0):\n",
    "                    print(i, j)\n",
    "                    dp[i][j] = 1\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1\n",
    "        print(dp)\n",
    "        return sum([sum(row) for row in dp])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        b=len(matrix)\n",
    "        a=len(matrix[0])\n",
    "        for i in range(a):\n",
    "            for j in range(b):\n",
    "                if i*j!=0 and int(matrix[j][i])==1:\n",
    "                    matrix[j][i]=1+min(int(matrix[j][i-1]),int(matrix[j-1][i-1]),int(matrix[j-1][i]))\n",
    "                else:\n",
    "                    matrix[j][i]=int(matrix[j][i])\n",
    "        return sum([matrix[j][i] for i in range(a) for j in range(b)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int: \n",
    "        res = 0\n",
    "        tmp = []\n",
    "        for j in range(len(matrix)):\n",
    "            for k in range(len(matrix[0])):\n",
    "                if matrix[j][k] == 1:\n",
    "                    res += 1\n",
    "                    tmp.append([j, k])\n",
    "\n",
    "        def iscube(n,i):\n",
    "            for m in range(n+1):\n",
    "                if matrix[i[0] + m][i[1]+ n] == 1 and  matrix[i[0]+ n][i[1] + m]:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        n = 1\n",
    "        while n < len(matrix) + 1:\n",
    "            tmp_list = tmp.copy()\n",
    "            tmp = []\n",
    "            for i in tmp_list:\n",
    "                if i[0] < len(matrix) - n and i[1] < len(matrix[0]) -n:\n",
    "                    if iscube(n, i):\n",
    "                        res += 1\n",
    "                        tmp.append(i)                                                         \n",
    "            n += 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        line = len(matrix)\n",
    "        row = len(matrix[0])\n",
    "        ans = 0\n",
    "        store = []\n",
    "        \n",
    "        for i in range(line):\n",
    "            store.append([])\n",
    "            for j in range(row):\n",
    "                store[i].append(matrix[i][j])\n",
    "                if matrix[i][j]==1:\n",
    "                    ans+=1\n",
    "        print(ans)\n",
    "        print(store)\n",
    "        \n",
    "        for edge in range(2, max(row, line)):\n",
    "            # print(f\"edge:{edge}\")\n",
    "            for i in range(line-1, edge-2, -1):\n",
    "                \n",
    "                for j in range(row-1, edge-2, -1):\n",
    "                    # print(f\"store:{store}\")\n",
    "                    \n",
    "                    temp = True\n",
    "                    if store[i-1][j-1]!=edge-1:\n",
    "                        # store[i][j]=0\n",
    "                        temp = False\n",
    "                        continue\n",
    "                    else:\n",
    "                        for k in range(i,i-edge,-1):\n",
    "                            if matrix[k][j]==0:\n",
    "                                temp = False\n",
    "                                break\n",
    "                        for k in range(j,j-edge,-1):\n",
    "                            if matrix[i][k]==0:\n",
    "                                temp = False\n",
    "                                break\n",
    "                        if temp:\n",
    "                            store[i][j]=edge\n",
    "                            ans+=1\n",
    "                            # print(f\"i:{i},j:{j},edge={edge}, ans={ans}\")\n",
    "            # print(f\"in edge:{edge}, ans = {ans}\")\n",
    "        print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0 :\n",
    "            return 0\n",
    "        \n",
    "\n",
    "        tot = [[0 for i in range(len(matrix[0])+1)] for j in range(len(matrix)+1)]\n",
    "        dp = copy.deepcopy(tot)\n",
    "        \n",
    "\n",
    "        for i in range(1, len(matrix)+1):\n",
    "            for j in range(1, len(matrix[0])+1):\n",
    "                tot[i][j] = tot[i-1][j] + tot[i][j-1] - tot[i-1][j-1] + matrix[i-1][j-1]\n",
    "\n",
    "        for i in range(1, len(matrix)+1):\n",
    "            for j in range(1, len(matrix[0])+1):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]\n",
    "            \n",
    "                for k in range(1, min(i, j)+1):\n",
    "                    if tot[i][j] - tot[i-k][j] - tot[i][j-k] + tot[i-k][j-k] == pow(k, 2):\n",
    "                        dp[i][j] += 1\n",
    "                    else:\n",
    "                        break\n",
    "        \n",
    "        return dp[len(matrix)][len(matrix[0])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        preSum = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                preSum[i+1][j+1] = preSum[i][j+1]+preSum[i+1][j]-preSum[i][j]+matrix[i][j]\n",
    "        def getRec(x1,y1,x2,y2):\n",
    "            return preSum[x2+1][y2+1]-preSum[x2+1][y1]-preSum[x1][y2+1]+preSum[x1][y1]\n",
    "        cnt = 0\n",
    "        print(preSum)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(1,min(m+1,n+1)):\n",
    "                    if i+k-1>=m or j+k-1>=n:break\n",
    "                    if getRec(i,j,i+k-1,j+k-1)==(k)*(k):\n",
    "                        cnt+=1\n",
    "                    else:\n",
    "                        break\n",
    "        return cnt\n",
    "                \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        row=len(matrix)\n",
    "        col=len(matrix[0])\n",
    "        matrix=[[int(i) for i in lst] for lst in matrix]\n",
    "        dp=[[0 for _ in range(col)] for _ in range(row)]\n",
    "        #第0行和第0列的dp结果\n",
    "        dp[0][0]=matrix[0][0]\n",
    "        max_matrix=0\n",
    "        for i in range(row):\n",
    "            dp[i][0]=matrix[i][0]\n",
    "            if dp[i][0]>max_matrix:\n",
    "                max_matrix=dp[i][0]\n",
    "        for j in range(col):\n",
    "            dp[0][j]=matrix[0][j]\n",
    "            if dp[0][j]>max_matrix:\n",
    "                max_matrix=dp[0][j]\n",
    "        \n",
    "        for i in range(1,row):\n",
    "            for j in range(1,col):\n",
    "                if matrix[i][j]==1:\n",
    "                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1\n",
    "                    max_matrix=max(dp[i][j],max_matrix)\n",
    "        res=0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                res+=dp[i][j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        dp =  [[0] * (cols + 1) for _ in range(rows + 1)]\n",
    "\n",
    "        dp[1][1] = matrix[0][0]\n",
    "        for i in range(0, rows):\n",
    "            for j in  range(0, cols):\n",
    "                dp[i+1][j+1] = matrix[i][j] + dp[i+1][j] + dp[i][j+1] - dp[i][j]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, rows + 1):\n",
    "            for j in range(1, cols + 1):\n",
    "                r, maxr = 2, min(i, j)\n",
    "                if maxr > 5 and maxr * maxr == dp[i][j] + dp[i-maxr][j-maxr] - dp[i-maxr][j] - dp[i][j-maxr]:\n",
    "                    ans += maxr\n",
    "                    print(maxr)\n",
    "                    continue\n",
    "\n",
    "                ans += matrix[i - 1][j - 1]\n",
    "                while r <= maxr:\n",
    "                    sums = dp[i][j] + dp[i-r][j-r] - dp[i-r][j] - dp[i][j-r]\n",
    "                    if sums == r * r:\n",
    "                        ans += 1\n",
    "                        r += 1\n",
    "                    else:\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        preSum = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                preSum[i+1][j+1] = preSum[i][j+1]+preSum[i+1][j]-preSum[i][j]+matrix[i][j]\n",
    "        def getRec(x1,y1,x2,y2):\n",
    "            return preSum[x2+1][y2+1]-preSum[x2+1][y1]-preSum[x1][y2+1]+preSum[x1][y1]\n",
    "        cnt = 0\n",
    "        print(preSum)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(min(m,n)):\n",
    "                    if i+k>=m or j+k>=n:break\n",
    "                    # print(getRec(i,j,i+k,j+k))\n",
    "                    if getRec(i,j,i+k,j+k)==(k+1)*(k+1):\n",
    "                        cnt+=1\n",
    "                    else:\n",
    "                        break\n",
    "        return cnt\n",
    "                \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        l,w=len(matrix),len(matrix[0])\n",
    "        a={(i,j) for i in range(l) for j in range(w) if matrix[i][j]==1}\n",
    "        c=0\n",
    "        result=[len(a)]\n",
    "        while l*w!=0:\n",
    "            c+=1\n",
    "            l-=1\n",
    "            w-=1\n",
    "            a={(p,q) for (p,q) in a if p<l and q<w and matrix[p+c][q+c]==1 and {(p+1,q),(p,q+1)}<=a}\n",
    "            result.append(len(a))\n",
    "        return sum(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\r\n",
    "        r, c = len(matrix), len(matrix[0])\r\n",
    "        pre = [[0] * (c + 1) for _ in range(r + 1)]\r\n",
    "        \r\n",
    "        for i in range(1, r + 1):\r\n",
    "            for j in range(1, c + 1):\r\n",
    "                pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1]\r\n",
    "        \r\n",
    "        res = 0\r\n",
    "        for i in range(r + 1):\r\n",
    "            for j in range(c + 1):\r\n",
    "                l = 1\r\n",
    "                while i + l <= r and j + l <= c and pre[i + l][j + l]-pre[i+l][j]-pre[i][j+l]+pre[i][j] == l * l:\r\n",
    "                    res += 1\r\n",
    "                    l += 1\r\n",
    "        return res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        rows, cols = len(matrix), len(matrix[0])\n",
    "        dp =  [[0] * (cols + 1) for _ in range(rows + 1)]\n",
    "\n",
    "        dp[1][1] = matrix[0][0]\n",
    "        for i in range(0, rows):\n",
    "            for j in  range(0, cols):\n",
    "                dp[i+1][j+1] = matrix[i][j] + dp[i+1][j] + dp[i][j+1] - dp[i][j]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, rows + 1):\n",
    "            for j in range(1, cols + 1):\n",
    "                ans += matrix[i - 1][j - 1]\n",
    "                r, maxr = 2, min(i, j)\n",
    "                while r <= maxr:\n",
    "                    sums = dp[i][j] + dp[i-r][j-r] - dp[i-r][j] - dp[i][j-r]\n",
    "                    if sums == r * r:\n",
    "                        ans += 1\n",
    "                        r += 1\n",
    "                    else:\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        prefix = [[0 for i in range(m + 1)] for j in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i - 1][j - 1]\n",
    "        #print(prefix)\n",
    "        ans = 0\n",
    "        r, c = 0, 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == 0:\n",
    "                    continue\n",
    "                for k in range(min(n - i, m - j)):\n",
    "                    r, c = i + k, j + k\n",
    "                    area = (k + 1) * (k + 1)\n",
    "                    if area == prefix[r + 1][c + 1] - prefix[r + 1][c - k] - prefix[r - k][c + 1] + prefix[r - k][c - k]:\n",
    "                        #print(i, j, r, c, length + 1, width + 1)\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\r\n",
    "        r, c = len(matrix), len(matrix[0])\r\n",
    "        pre = [[0] * (c + 1) for _ in range(r + 1)]\r\n",
    "        \r\n",
    "        for i in range(1, r + 1):\r\n",
    "            for j in range(1, c + 1):\r\n",
    "                pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1]\r\n",
    "        \r\n",
    "        res = 0\r\n",
    "        for i in range(r + 1):\r\n",
    "            for j in range(c + 1):\r\n",
    "                l = 1\r\n",
    "                while i + l <= r and j + l <= c and pre[i + l][j + l]-pre[i+l][j]-pre[i][j+l]+pre[i][j] == l * l:\r\n",
    "                    res += 1\r\n",
    "                    l += 1\r\n",
    "        return res\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        prefix = [[0 for i in range(m + 1)] for j in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i - 1][j - 1]\n",
    "        #print(prefix)\n",
    "        ans = 0\n",
    "        r, c = 0, 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == 0:\n",
    "                    continue\n",
    "                for k in range(min(n - i, m - j)):\n",
    "                    r, c = i + k, j + k\n",
    "                    area = (k + 1) * (k + 1)\n",
    "                    if area == prefix[r + 1][c + 1] - prefix[r + 1][c - k] - prefix[r - k][c + 1] + prefix[r - k][c - k]:\n",
    "                        #print(i, j, r, c, length + 1, width + 1)\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        l=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        dp = [[0 for i in range(n)] for j  in range(l)]\n",
    "        def bfs(i,j,dep):\n",
    "            dep=dep+1\n",
    "            for k in range(0,dep):\n",
    "                if(i+k>=l or j+dep-1>=n or i+dep-1>=l or j+k>=n):\n",
    "                    return dep-1\n",
    "                if matrix[i+k][j+dep-1]==1 and matrix[i+dep-1][j+k]==1:\n",
    "                    continue\n",
    "                else:\n",
    "                    return dep-1\n",
    "     \n",
    "            return bfs(i,j,dep)\n",
    "\n",
    "\n",
    "        for i in range(l):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==0:\n",
    "                    dp[i][j]==0\n",
    "                else:\n",
    "                    t=bfs(i,j,1)\n",
    "                    dp[i][j]=t\n",
    "        s=0\n",
    "        for i in dp:\n",
    "            print(i)\n",
    "            s=s+sum(i)\n",
    "        return s       \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        l=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        dp = [[0 for i in range(n)] for j  in range(l)]\n",
    "        def bfs(i,j,dep):\n",
    "            dep=dep+1\n",
    "            for k in range(0,dep):\n",
    "                if(i+k>=l or j+dep-1>=n or i+dep-1>=l or j+k>=n):\n",
    "                    return dep-1\n",
    "                if matrix[i+k][j+dep-1]==1 and matrix[i+dep-1][j+k]==1:\n",
    "                    continue\n",
    "                else:\n",
    "                    return dep-1\n",
    "     \n",
    "            return bfs(i,j,dep)\n",
    "\n",
    "\n",
    "        for i in range(l):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]==0:\n",
    "                    dp[i][j]==0\n",
    "                else:\n",
    "                    t=bfs(i,j,1)\n",
    "                    dp[i][j]=t\n",
    "        s=0\n",
    "        for i in dp:\n",
    "            print(i)\n",
    "            s=s+sum(i)\n",
    "        return s       \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        def sum_son_matrix(matrix, i, j, k):\n",
    "            sum = 0\n",
    "            for temp_1 in range(i-k, i+1):\n",
    "                for temp_2 in range(j-k, j+1):\n",
    "                    sum += matrix[temp_1][temp_2]\n",
    "            return sum\n",
    "        \n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        result = [[0] * (n + 1) for i in range(m + 1)]\n",
    "\n",
    "        # 第一个矩阵，以元素dp[i][j]结尾的最大正方形的阶数\n",
    "        \n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                temp = min(i, j) - 1\n",
    "                k = 0\n",
    "                while k <= temp:\n",
    "                    if sum_son_matrix(matrix, i-1, j-1, k) == (k+1) ** 2:\n",
    "                        k += 1\n",
    "                    else:\n",
    "                        break\n",
    "                new = k\n",
    "                print(i,j,new)\n",
    "                result[i][j] = result[i-1][j] + result[i][j-1] - result[i-1][j-1] + new \n",
    "        print(result)\n",
    "        return result[-1][-1]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, mat: List[List[int]]) -> int:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        h=[]\n",
    "        for i in range(m):\n",
    "            h.append([0]*n+[1])\n",
    "            for j in range(n):\n",
    "                if mat[i][j]==0:\n",
    "                    h[i][j]=0\n",
    "                else:\n",
    "                    h[i][j] = (h[i-1][j]+1) if i-1>=0 else 1\n",
    "        hp = []\n",
    "        for i in range(m):\n",
    "            hp.append([-1]*(n+1))\n",
    "            st = [-1]\n",
    "            for j in range(n+1):\n",
    "                if h[i][j]==0:\n",
    "                    st=[j]\n",
    "                hp[i][j]=st[-1]\n",
    "        ans=0\n",
    "        dp=[]\n",
    "        for i in range(m):\n",
    "            dp.append([0]*n)\n",
    "            for j in range(n):\n",
    "                dp[i][j]=mat[i][j]\n",
    "                pre=dp[i-1][j-1] if i-1>=0 and j-1>=0 else 0\n",
    "                dp[i][j]=min(pre+1, h[i][j], j-hp[i][j])\n",
    "                # if h[i][j]>=pre+1:\n",
    "                #     if j-hp[i][j]>=pre+1:\n",
    "                #         dp[i][j]=pre+1\n",
    "                ans+=dp[i][j]\n",
    "            # print(mat[i], h[i], hp[i], dp[i])\n",
    "        # #        #\n",
    "        # ##      ##\n",
    "        # ###   ####\n",
    "        # ####  ####\n",
    "        # ##########\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, g: List[List[int]]) -> int:\n",
    "        m, n = len(g), len(g[0])\n",
    "        R = min(n, m)\n",
    "        presum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        # presum\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                presum[i][j] = presum[i - 1][j] + presum[i][j-1] - presum[i - 1][j - 1] + g[i-1][j-1]\n",
    "        print(presum)\n",
    "        ans = 0\n",
    "        for L in range(1, R + 1):\n",
    "            for i in range(L, m + 1):\n",
    "                for j in range(L, n + 1):\n",
    "                    curS = presum[i][j] - presum[i - L][j] - presum[i][j - L] + presum[i - L][j - L]\n",
    "                    ans += (curS == L * L)\n",
    "        print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        directions = [(-1,0), (1,0),(0,-1),(0,1)]\n",
    "        develop = [(1,0), (1,1),(0,1)]\n",
    "\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "\n",
    "        visited = [[0] * m for _ in range(n)]\n",
    " \n",
    "        def dfs(x, y):\n",
    "            # print(x,y)\n",
    "            visited[x][y] = 1\n",
    "            min_w = 305\n",
    "            for di, dj in develop:\n",
    "                ni, nj = x + di, y + dj\n",
    "                \n",
    "                if 0<=ni<n and 0<=nj<m and matrix[ni][nj]>0:\n",
    "                    if visited[ni][nj] == 0:\n",
    "                        dfs(ni, nj)                 \n",
    "                    min_w = min(min_w, matrix[ni][nj])\n",
    "                    # print('d: ',ni, nj, matrix[ni][nj])\n",
    "                    # min_w.append(matrix[ni][nj])\n",
    "                    \n",
    "                else:\n",
    "                    min_w = 0\n",
    "                    # min_w.append(0)\n",
    "                \n",
    "                # print(x, y, ni, nj, min_w)\n",
    "                \n",
    "            # min_w = min(min_w)\n",
    "            # print(x, y, min_w)\n",
    "            if min_w == 305:\n",
    "                min_w = 0\n",
    "            matrix[x][y] += min_w\n",
    "            self.ans += matrix[x][y] \n",
    "\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == 1 and visited[i][j] == 0:\n",
    "                    dfs(i,j)\n",
    "\n",
    "        # print(matrix)\n",
    "\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        dp = [[None for _ in range(len(matrix[0]))] for _ in range(len(matrix))]\n",
    "        def dfs(i, j):\n",
    "            nonlocal matrix\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            if i == 0 or j == 0:\n",
    "                if dp[i][j] is None:\n",
    "                    dp[i][j] = matrix[i][j]\n",
    "                return dp[i][j]\n",
    "            if dp[i-1][j-1] is None:\n",
    "                dp[i-1][j-1] = dfs(i-1, j-1)\n",
    "            if dp[i][j-1] is None:\n",
    "                dp[i][j-1] = dfs(i, j-1)\n",
    "            if dp[i-1][j] is None:\n",
    "                dp[i-1][j] = dfs(i-1, j)\n",
    "            if matrix[i][j]: \n",
    "                dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1\n",
    "            else:\n",
    "                dp[i][j] = 0\n",
    "            return dp[i][j]\n",
    "        dfs(len(matrix)-1, len(matrix[0])-1)\n",
    "        return sum([sum(x) for x in dp])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        ans = set()\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        \n",
    "        def check(x, y):\n",
    "            floor = min(m-x, n-y)\n",
    "            \n",
    "            for p in range(1, floor):\n",
    "                for i in range(x, x+p+1):\n",
    "                    # print(x, y, p, (i, y+p),matrix[i][y+p])\n",
    "                    if matrix[i][y+p] != 1:\n",
    "                        ans.add(tuple([x, y, p]))\n",
    "                        return\n",
    "                for j in range(y, y+p):\n",
    "                    # print(x, y, p, (x+p, j),matrix[x+p][j])\n",
    "                    if matrix[x+p][j] != 1:\n",
    "                        ans.add(tuple([x, y, p]))\n",
    "                        return\n",
    "                ans.add(tuple([x, y, p]))\n",
    "            ans.add(tuple([x, y, floor]))\n",
    "            return\n",
    "            \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 1:\n",
    "                    check(i, j)\n",
    "        # print(ans)\n",
    "        \n",
    "        return len(ans)\n",
    "            \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        left,up=[[0]*n for _ in range(m)],[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(1,n):\n",
    "                if matrix[i][j-1] == 1:\n",
    "                    left[i][j]=1 + left[i][j-1]\n",
    "        for j in range(n):\n",
    "            for i in range(1,m):\n",
    "                if matrix[i-1][j] == 1:\n",
    "                    up[i][j] = up[i-1][j] +1 \n",
    "        ans = 0 \n",
    "        dp = [[0]*n for _ in range(m)] \n",
    "        for i in range(n):\n",
    "            dp[0][i] = matrix[0][i]\n",
    "            if matrix[0][i] == 1:\n",
    "                ans += 1\n",
    "        for i in range(m):\n",
    "            dp[i][0]= matrix[i][0]\n",
    "            if matrix[i][0] == 1:\n",
    "                ans += 1\n",
    "        if matrix[0][0]==1:\n",
    "            ans -= 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if matrix[i][j] == 1:\n",
    "                    dp[i][j] = min(dp[i-1][j-1],left[i][j],up[i][j])+1\n",
    "                    ans += dp[i][j]\n",
    "        return ans \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        l,w=len(matrix),len(matrix[0])\n",
    "        a=[(i,j) for i in range(l) for j in range(w) if matrix[i][j]==1]\n",
    "        a=set(a)\n",
    "        c=0\n",
    "        result=[len(a)]\n",
    "        while l*w!=0:\n",
    "            c+=1\n",
    "            l-=1\n",
    "            w-=1\n",
    "            a=[(p,q) for (p,q) in a if p<l and q<w and matrix[p+c][q+c]==1 and {(p+1,q),(p,q+1)}<=a]\n",
    "            a=set(a)\n",
    "            result.append(len(a))\n",
    "        return sum(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0]) if len(matrix) > 0 else 0\n",
    "        if m == 0 or n == 0:\n",
    "            return 0\n",
    "        dp_row = [[0]*(n+1) for _ in range(m+1)]\n",
    "        dp_col = [[0]*(n+1) for _ in range(m+1)]\n",
    "        dp_mat = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if matrix[i-1][j-1] == 1:\n",
    "                    dp_row[i][j] = dp_row[i][j-1] + 1\n",
    "                    dp_col[i][j] = dp_col[i-1][j] + 1\n",
    "                    dp_mat[i][j] = min([dp_mat[i-1][j-1]+1, dp_row[i][j], dp_col[i][j]])\n",
    "                else:\n",
    "                    dp_row[i][j] = 0\n",
    "                    dp_col[i][j] = 0\n",
    "                    dp_mat[i][j] = 0\n",
    "        # for it in dp_row:\n",
    "        #     print(it)\n",
    "        # print()\n",
    "        # for it in dp_col:\n",
    "        #     print(it)\n",
    "        result = 0\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                length = min([dp_row[i][j], dp_col[i][j], dp_mat[i][j]])\n",
    "                result += length\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        table = {}\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == 1:\n",
    "                    self.search(i, j, matrix, table)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == 1:\n",
    "                    res += table[(i, j)]\n",
    "        return res\n",
    "\n",
    "    def search(self, i, j, matrix, table):\n",
    "        if (i, j) not in table:\n",
    "            n, m = len(matrix), len(matrix[0])\n",
    "            if i == n - 1 or j == m - 1:\n",
    "                table[(i, j)] = 1\n",
    "            else:\n",
    "                if matrix[i + 1][j] == 1 and matrix[i][j + 1] == 1 and matrix[i + 1][j + 1] == 1:\n",
    "                    table[(i, j)] = 1 + min(self.search(i + 1, j, matrix, table), self.search(i, j + 1, matrix, table), self.search(i + 1, j + 1, matrix, table))\n",
    "                else:\n",
    "                    table[(i, j)] = 1\n",
    "        return table[(i, j)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        square = {}\n",
    "\n",
    "        for i in range(0, len(matrix)):\n",
    "            for j in range(0, len(matrix[0])):\n",
    "                if matrix[i][j] == 1:\n",
    "                    square[(i, j)] = min(square.get((i-1, j-1), 0), square.get((i-1, j), 0), square.get((i, j-1), 0)) + 1\n",
    "        return sum(square.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        square = {}\n",
    "\n",
    "        for j in range(len(matrix[0])):\n",
    "            if matrix[0][j] == 1:\n",
    "                square[(0, j)] = 1\n",
    "\n",
    "        for i in range(len(matrix)):\n",
    "            if matrix[i][0] == 1:\n",
    "                square[(i, 0)] = 1\n",
    "\n",
    "        for i in range(1, len(matrix)):\n",
    "            for j in range(1, len(matrix[0])):\n",
    "                if matrix[i][j] == 1:\n",
    "                    # square.add((i, j, 1))\n",
    "                    # for k in range(2, i+2): ## \n",
    "                    cursize = square.get((i-1, j-1), 0)\n",
    "                    cursize = min(cursize, square.get((i-1, j), 0))\n",
    "                    cursize = min(cursize, square.get((i, j-1), 0))\n",
    "                    square[(i, j)] = cursize+1\n",
    "\n",
    "        # print(square)\n",
    "        return sum(square.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        pre_matrix = [[0]*n for _ in range(m)]\n",
    "        pre_matrix[0][0] = matrix[0][0]\n",
    "        for j in range(1, n):\n",
    "            pre_matrix[0][j] = pre_matrix[0][j-1]+matrix[0][j]\n",
    "        for i in range(1, m):\n",
    "            pre_matrix[i][0] = pre_matrix[i-1][0] + matrix[i][0]\n",
    "            row_sum = matrix[i][0]\n",
    "            # print(i,j, row_sum)\n",
    "            for j in range(1, n):\n",
    "                row_sum = row_sum + matrix[i][j]\n",
    "                pre_matrix[i][j] = pre_matrix[i-1][j] + row_sum\n",
    "        # print(pre_matrix)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sq = min(i, j) + 1\n",
    "                for k in range(1, sq+1):\n",
    "                    top = pre_matrix[i-k][j] if i-k>=0 else 0\n",
    "                    left = pre_matrix[i][j-k] if j-k>=0 else 0\n",
    "                    center = pre_matrix[i-k][j-k] if i-k>= 0 and j-k >=0 else 0\n",
    "                    area = pre_matrix[i][j] - top - left + center\n",
    "                    if area == k*k:\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        pre = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + matrix[i][j]\n",
    "        ans = 0\n",
    "        for x0 in range(n):\n",
    "            for y0 in range(m):\n",
    "                k = 0\n",
    "                while x0 + k < n and y0 + k < m:\n",
    "                    x1, y1 = x0 + k, y0 + k\n",
    "                    if pre[x1 + 1][y1 + 1] - pre[x1 + 1][y0] - pre[x0][y1 + 1] + pre[x0][y0] == (k + 1) * (k + 1):\n",
    "                        ans += 1\n",
    "                    k += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m, n, res = len(matrix), len(matrix[0]), 0\n",
    "        sm = [[0] * (n + 1) for i in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sm[i + 1][j + 1] = sm[i][j + 1] + sm[i + 1][j] + matrix[i][j] - sm[i][j]\n",
    "        for i in range(2, min(m, n) + 1):\n",
    "            for j in range(m - i + 1):\n",
    "                for k in range(n - i + 1):\n",
    "                    if matrix[j][k] == 1:\n",
    "                        tj, tk = j + i, k + i\n",
    "                        if sm[tj][tk] - sm[j][tk] - sm[tj][k] + sm[j][k] == i * i:\n",
    "                            res += 1\n",
    "        return res + sm[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        s = [[0] * (n+1) for _ in range(m+1)]\n",
    "        sum = 0\n",
    "        for i in range(1,m+1):\n",
    "            sum += matrix[i-1][0]\n",
    "            s[i][1] = sum\n",
    "        sum = 0\n",
    "        for j in range(1,n+1):\n",
    "            sum += matrix[0][j-1]\n",
    "            s[1][j] = sum\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + matrix[i][j]\n",
    "        mina = min(m,n)\n",
    "        count = 0\n",
    "\n",
    "        for x in range(1,mina + 1):\n",
    "            for i in range(m-x+1):\n",
    "                for j in range(n-x+1):\n",
    "                    if(self.countSquares2(s,i,j,i+x-1,j+x-1) == x*x):\n",
    "                        count +=1\n",
    "        return count\n",
    "    def countSquares2(self,s: List[List[int]],lcol,lrow,rcol,rrow):\n",
    "        return s[rcol+1][rrow+1]-s[rcol+1][lrow] - s[lcol][rrow+1] + s[lcol][lrow]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        \n",
    "        r, c = len(matrix), len(matrix[0])\n",
    "        \n",
    "        dp = [[0] * (c + 1) for _ in range(r + 1)]\n",
    "        \n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(1, len(dp[0])):\n",
    "                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1]\n",
    "                \n",
    "                \n",
    "        res = 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                for d in range(1, min(i + 1, j + 1) + 1):\n",
    "                    delta = d - 1\n",
    "                    top, left = i - delta, j - delta\n",
    "                    bot, right = i, j\n",
    "                    \n",
    "                    if dp[bot + 1][right + 1] - (dp[bot + 1][left] + dp[top][right + 1] - dp[top][left]) == d * d:\n",
    "                        res += 1\n",
    "                    \n",
    "        return res\n",
    "                    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        pre = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        cnt = 0\n",
    "        ans = 0 \n",
    "        for i in range(m):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                cnt+=matrix[i][j]\n",
    "                pre[i+1][j+1] = pre[i][j+1]+cnt\n",
    "                if matrix[i][j] ==1:\n",
    "                    for k in range(1,min(i+1,j+1)+1):\n",
    "                        if (pre[i+1][j+1] - pre[i+1][j-k+1]-pre[i+1-k][j+1]+pre[i+1-k][j+1-k]) ==k**2:\n",
    "                            ans+=1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        ms = MatrixSum(matrix)\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        ans = 0\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, v in enumerate(row):\n",
    "                for k in range(1, min(m - i, n - j) + 1):\n",
    "                    t = ms.query(i, j, i + k, j + k)\n",
    "                    if t < k ** 2:\n",
    "                        break\n",
    "                    ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "class MatrixSum:\n",
    "    def __init__(self, matrix: List[List[int]]):\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, v in enumerate(row):\n",
    "                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + v\n",
    "        self.s = s\n",
    "\n",
    "    def query(self, r1: int, c1: int, r2: int, c2: int) -> int:\n",
    "        return self.s[r2][c2] - self.s[r2][c1] - self.s[r1][c2] + self.s[r1][c1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        ms = MatrixSum(matrix)\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for l in range(min(m, n)):\n",
    "                    t = (l+1)*(l+1)\n",
    "                    if(matrix[i][j] == 0):\n",
    "                        break\n",
    "                    if(i+l >= m or j+l >= n):\n",
    "                        break\n",
    "                    if(ms.query(i, j, i+l, j+l) == t):\n",
    "                        res += 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "class MatrixSum:\n",
    "    def __init__(self, matrix: List[List[int]]):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        s = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, x in enumerate(row):\n",
    "                s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + x\n",
    "        \n",
    "        self.s = s\n",
    "\n",
    "    def query(self, r1, c1, r2, c2):\n",
    "        return self.s[r2+1][c2+1] - self.s[r2+1][c1] - self.s[r1][c2+1] + self.s[r1][c1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSquares(self, matrix: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "            m*n 矩阵  \n",
    "        \"\"\"\n",
    "\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        f=[[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                f[i][j] = f[i-1][j]+f[i][j-1]-f[i-1][j-1]+matrix[i-1][j-1]\n",
    "        ans = 0 \n",
    "        # for i in range(m+1):\n",
    "            # print(f[i])\n",
    "        for L in range(1,min(m,n)+1):\n",
    "            for i in range(0,m-L+1):\n",
    "                for j in range(0,n-L+1):\n",
    "                    if f[i+L][j+L]-f[i][j+L]-f[i+L][j]+f[i][j] == L*L:\n",
    "                        # print(\"坐标({},{}), 边长{}\".format(i,j,L))\n",
    "                        ans+=1\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
